package LeetCode;

import java.util.*;
import java.util.stream.IntStream;

public class LeetCodeMain22 {
    public int maxProfit(int[] prices) {
        int sum=0;
        for (int i = 0; i < prices.length-1; i++) {
            sum+=Math.max(0,prices[i+1]-prices[i]);
        }
        return sum;
    }
    public boolean isTree(TreeNode root1,TreeNode root2){
        if ((root1==null&&root2!=null)||(root1!=null&&root2==null)){
            return false;
        }
        if (root1.val!=root2.val){
            return false;
        }
        if (root1==null&&root2==null){
            return true;
        }
        return isTree(root1.left,root2.right)&&isTree(root1.right,root2.left);
    }
    public boolean isSymmetric(TreeNode root) {
        return isTree(root.left,root.right);
    }
    List<Integer> list3=new ArrayList<>();
    List<Integer> list4=new ArrayList<>();
    public void perorder(TreeNode root,List<Integer> list){
        if (root==null){
            return;
        }
        if (root.left==null&& null == root.right){
            list.add(root.val);
        }
        perorder(root.left,list);
        perorder(root.right,list);

    }
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1=new ArrayList<>();
        List<Integer> list2=new ArrayList<>();
        perorder(root1,list3);
        perorder(root2,list4);
        list1=list3;
        list2=list4;
        boolean flag=list1.size()==list2.size();
        for (int i = 0; i < list1.size()&&flag; i++) {
            if (list1.get(i)!=list2.get(i)){
                flag=false;
            }
        }
        if (flag==false){
            return false;
        }
        return true;
    }
    public TreeNode increasingBST(TreeNode root) {
        List<TreeNode> list=new ArrayList<>();
        inorder(root,list);
        TreeNode one=new TreeNode(-1);
        TreeNode two=one;
        int count=0;
        while (count<list.size()){
            two.right=list.get(count);
            two=two.right;
            two.left=null;
            count++;
        }
        return one.right;
    }
    public void inorder(TreeNode root,List<TreeNode> list){
        if (root==null){
            return;
        }
        inorder(root.left,list);
        list.add(root);
        inorder(root.right, list);
    }

    public TreeNode invertTree(TreeNode root) {
        if (root==null){
            return root;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
    public int minDepth(TreeNode root) {
        if (root==null){
            return 0;
        }
        if (root.left==null&&root.right==null){
            return 1;
        }
        int min=Integer.MAX_VALUE;
        if (root.left!=null){
            min=Math.min(minDepth(root.left),min);
        }
        if (root.right!=null){
            min=Math.min(minDepth(root.right),min);
        }
        return min+1;
    }
    HashSet<Integer> set=new HashSet<>();
    public void perorder(TreeNode root){
        if (root==null){
            return;
        }
        set.add(root.val);
        perorder(root.left);
        perorder(root.right);
    }
    public int numColor(TreeNode root) {
        perorder(root);
        return set.size();
    }
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root==null){
            return false;
        }
        return isPath(0,root,targetSum);
    }
    public boolean isPath(int sum,TreeNode root,int targetSum){
        if (root==null){
            return false;
        }
        sum+=root.val;
        if (root.left==null&&root.right==null&&sum==targetSum){
            return true;
        }
        return isPath(sum, root.left, targetSum)||isPath(sum, root.right, targetSum);
    }
    public boolean canJump(int[] nums) {
        int cover=0;
        if (nums.length==1){
            return true;
        }
        for (int i = 0; i <= cover; i++) {
            cover=Math.max(cover,i+nums[i]);
            if (cover>=nums.length-1){
                return true;
            }
        }
        return false;
    }
    public int largestSumAfterKNegations1(int[] nums, int k) {
        nums = IntStream.of(nums)
                .boxed()
                .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                .mapToInt(Integer::intValue).toArray();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            //从前向后遍历，遇到负数将其变为正数，同时K--
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        if (k%2==1){
            nums[len-1]=-nums[len-1];
        }
        return Arrays.stream(nums).sum();
    }
    public int largestSumAfterKNegations(int[] nums, int k) {
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        for (int num:nums) {
            queue.offer(num);
        }
        int sum=0;
        while (k>0){
            int min=-queue.poll();
            queue.offer(min);
            k--;
        }
        for (int num:queue) {
            sum+=num;
        }
        return sum;
    }

    }
